package com.jml.排序;


/**
 * @author:jml
 * @date: 2020/3/28 0028 15:17
 * @description： 思想：将一个数组划分为两个数组，然后通过递归调用自身不停的再进行划分，直到划分不下去进行排序
 * 如何划分数组:设置关键字，比关键字小的数组放在一组，比关键字大的放在一组
 * 如何设置关键字：设置数组最右边的数据为关键字 如果设置最右边的数字为关键字，那么最右边的元素应该从倒数第二个数字开始，而不是从最后一个开始
 */
public class my快速排序 {

    public static void main(String[] args) {
        long[] arr = new long[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = (long) (Math.random() * 99);
        }
        disPlay(arr);
        //传的是索引，所以要-1
        //partition(arr, 0, arr.length - 1, arr[arr.length - 1]);
        sort(arr, 0, arr.length-1);
        disPlay(arr);
    }

    /**
     * 88   100......90      120 假设关键字是99 从左边开始，因为100大于指针到100的位置停下来 然后从右边开始，因为90小于99指针到90就停下来，然后将左边的指针和右边的指针进项交换
     * 88   90......100     120 然后左边指针又往前面，直到碰到比关键字大的数字就停下来，接着右边也继续往前走，碰到关键字小的就停止下来，然后交换位置，左边继续往前走
     *
     * @param arr 传递一个数组
     * @param left 数组的最左边的索引
     * @param right 数组的最右边的索引 如果设置最右边的数字为关键字，那么最右边的元素应该从倒数第二个数字开始，而不是从最后一个开始
     * 最后再把最后一个元素和结束之后的左边指针或者右边指针进行交换
     * @param point 关键字 第一次进入left= -1 ，right = arr.length+1,因为把最后一个元素当做关键字，所以right = arr.length
     */
    public static int partition(long arr[], int left, int right, long point) {
        int leftPre = left - 1;
        int rightPre = right;
        while (true) {
            //最后结束时就是leftPre=rightPre
            //从左边开始，小于关键字的就进入循环,碰到小于关键字的就继续,碰到大于关键字的就停下来
            while (leftPre < rightPre && arr[++leftPre] < point) {
                ;
            }
            //从右边开始，大于关键字的就进入循环,碰到大于关键字的就继续,碰到小于关键字的就停下来
            while (leftPre < rightPre && arr[--rightPre] > point) {
                ;
            }
            //然后进行交换位置
            if (leftPre >= rightPre) {
                break;
            } else {
                //进行交换
                long tmp = arr[leftPre];
                arr[leftPre] = arr[rightPre];
                arr[rightPre] = tmp;
            }
        }
        //将关键字和当前leftPre所指的进行交换
        long tmp1 = arr[leftPre];
        arr[leftPre] = arr[right];
        arr[right] = tmp1;
        System.out.println(leftPre);
        System.out.println(rightPre);
        return leftPre;
    }


    public static void sort(long[] arr, int left, int right) {
        if(right<=left){
            return;
        }
        //设置关键字
        long point = arr[right];
        //获取切入点，同时对数组进行划分
        int partition = partition(arr, left, right, point);
        //递归对左边的子数组当成一个新数组进行分组
        sort(arr, left, partition - 1);
        //递归对右边的子数组当成一个新数组进行分组
        sort(arr, partition + 1, right);
    }


    public static void disPlay(long arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ,");
        }
        System.out.println("");
        System.out.println("----------------------------------------");
    }
}
